// 反转链表

#include <vector>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    // 解法一：暴力解法。遍历要被进反转的链表，储存每个节点的val，然后再重新遍历链表将其节点val值更改
    ListNode *reverseList1(ListNode *head)
    {
        if (nullptr == head) // 考虑链表为空的时候！
        {
            return head;
        }
        ListNode *reversehead = head;
        vector<int> v;
        while (reversehead != nullptr)
        {
            v.push_back(reversehead->val);
            reversehead = reversehead->next;
        } // reversehead == nullptr
        reversehead = head;
        int size = v.size();
        while (reversehead != nullptr)
        {
            reversehead->val = v[size - 1];
            size--;
            reversehead = reversehead->next;
        }
        return head;
    }

    // 解法二：迭代法。在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，
    //因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

    ListNode *reverseList2(ListNode *head)
    {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while (curr)
        {
            ListNode *next = curr->next; // 保存curr的下一个节点
            curr->next = prev;           // 使curr->next等于prev
            prev = curr;
            curr = next;
        }
        return prev;
    }
};